package com.leetcode.lianbiao;

/**
 * fd..
 *
 * @author Lizhong
 * @date 2019/9/7
 */

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNodde2 = new ListNode(2);
        ListNode listNodde3 = new ListNode(3);
        ListNode listNodde4 = new ListNode(4);
        listNode1.next = listNodde2;
        listNodde2.next = listNodde3;
        listNodde3.next = listNodde4;
        Solution solution = new Solution();
        ListNode listNode = solution.removeNthFromEnd(listNode1, 1);

    }
}

class Solution {
    /**
     * s双指针
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd02(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        // Advances first pointer so that the gap between first and second is n nodes apart
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
            if(first==null) return dummy.next;
        }
        // Move first to the end, maintaining the gap
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = head;

        if (head == null) return null;
        int m = 1;
        for (; temp.next != null; m++) temp = temp.next;
        if (n == m) return head.next;

        temp = head;
        for (int i = 0; i < m; i++) {

            if (i == (m - n - 1)) {

                temp.next = temp.next.next;
                break;
            }
            temp = temp.next;
        }
        return head;
    }
}
